//给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 
//
// 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
//
//与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
// 
// Related Topics 数组 双指针

package com.yun.leetcode.editor.cn;

// 【16】 最接近的三数之和
public class ThreeSumClosest {
    public static void main(String[] args) {
        Solution solution = new ThreeSumClosest().new Solution();
        int[] nums = {-1,2,1,-4};
        System.out.println(solution.threeSumClosest(nums, 1));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums.length - i - 1; j++) {
                    if (nums[j] > nums[j + 1]) {
                        int temp = nums[j + 1];
                        nums[j + 1] = nums[j];
                        nums[j] = temp;
                    }
                }
            }
            int diff = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {

                for (int l = i + 1, r = nums.length - 1; l < r; ) {
                    int sum = nums[i] + nums[l] + nums[r];
                    if (sum > target) {
                        r--;
                    } else if (sum < target) {
                        l++;
                    } else {
                        return sum;
                    }
                    diff = Math.abs(sum - target) < Math.abs(diff) ? (sum - target) : diff ;
                }
            }
            return target + diff;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}